package 笔试.Shopee;

public class 挑选商品 {
    static class Solution {

        /**
         * Note: 类名、方法名、参数名已经指定，请勿修改
         *
         * @param goods_list int整型 一维数组 商品价值
         * @param balance    int整型  余额
         * @return int整型
         */
        public int pickGoods(int[] goods_list, int balance) {
            int[] res = {0};
            dfs(goods_list, 0, 0, balance, res);
            return res[0];
        }

        private void dfs(int[] goodsList, int index, int sum, int balance, int[] res) {
            if (sum > balance) {
                return;
            } else if (sum > res[0]) {
                res[0] = sum;
            }
            for (int i = index; i < goodsList.length; i++) {
                dfs(goodsList, i + 1, sum + goodsList[i], balance, res);
            }
        }

    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] goods_list = {1500, 800, 200};
        int balance = 1600;
        System.out.println(solution.pickGoods(goods_list, balance));
    }
}
